



		RUBIK - SOLUTIE
	       ------------------

	Daca s-ar cunoate valoarea la care trebuie sa se ajunga, problema s-ar
reduce la rezolvarea unui sitem de m*n ecuatii cu m*n necunoscute. Fiecarei ecuatii
i-ar corespunde un element al grilei, valoarea finala a fiecarui element fiind obti-
nuta adunand la valoarea sa initiala numarul obtinut prin insumarea numerelor k, co-
respunzatoare operatiilor de pe pozitia sa si a vecinilor sai pe verticala sau ori-
zontala. Deci, in principiu, o ecuatie ar avea forma b(i,j)=a(i,j)+k(i,j)+k(i-1,j)+
+k(i+1,j)+k(i,j-1)+k(i,j+1)., unde b(i,j) este valoarea finala cxare trebuie obti-
nuta pentru toate elementele grilei, a(i,j) este valoarea initiala a elementului, iar
k(x,y) valoarea adunata pentru operatia efectuata asupra pozitiei (x,y). Singurele
ecuatii care nu au aceasta forma sunt cele corespunzatoare pozitiilor de pe marginea
grilei, caz in care vom avea doua elemente in ecuatie (daca avel o grila cu o singura
linie sau o singura coloana, pentru elementele de la extreme), trei elemente (pentru
restul elementelor dintr-o grila cu o singura linie sau o singura coloana si pentru
elementele din colturile unei grile "normale") sau 4 elemente (pt. elementele de pe
marginea unei grile "normale").
	In mod normal, ar trebuie sa rezolvam un sistem de maxim n=10.000 de ecuatii,
fiecare avand maxim k=5 necunoscute si exista algoritmi numerici care rezolva astfel
de sisteme (dupa transformarea sistemului in unul echivalent care respecta anumite
conditii) intr-un timp de ordinul O(m*k).
	Datorita faprului ca sistemul rezultat este unul particular, el poate fi
transformat intr-unul echivalent care sa aiba maxim 100 de ecuatii, fiecare avand
maxim 100 de necunoscute, sistem care poate fi rezolvat intr-un timp acceptabil, folo-
sind o metoda standard cum ar fi cea a lui Gauss.
	Tot ceea ce am spus anterior este valabil numai daca am cunoaste valoarea care
trebuie obtinuta pentru elementele grilei, ceea ce nu este cazul nostru. Totusi stim
ca aceasta valoare este un numar natural cuprins intre 1 si 1000, deci am putea sa in-
cercam sa rezolvam sistemul pentru toate aceste valori posibile. Dar daca vom verifica
pentru toate cele 1000 de valori, timpul de executie ar creste de 1000 de ori, iar
programul nu se va mai executa intr-un timp acceptabil. O posibila solutie ar fi sa in-
cercam sa "ghicim" care ar fi valoarea la care trebuie sa se ajunga. Datorita faptului
ca printr-o operatie elementele grilei pot sa creasca sau sa descreasca, pe cazul mediu
valoarea care trebuie obtinuta ar trebuie sa fie apropiata de media elementelor grilei
initiale. Evident, acest lucru nu este valabil pentru toate cazurile deoarece, daca trebuie
efectuate operatii pentru care valorile k au toate acelasi semn si sunt relativ mari in
valoarea absoluta, valoarea care trebuie obtinuta nu mai este apropiata de media elemen-
telor.